package com.cqs.leetcode.search;

import java.util.ArrayList;
import java.util.List;

/**
 * lixw
 * 2023/10/13
 */
public class Solution658 {

    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int base = findBase(arr, x), l = base - 1, r = base + 1;
        while (--k > 0) {
            boolean isLeft = r > arr.length - 1 || (l >= 0 && x - arr[l] <= arr[r] - x);
            if (isLeft) {
                l--;
            } else {
                r++;
            }
        }
        List<Integer> list = new ArrayList<>();
        for (int i = l + 1; i < r; i++) {
            list.add(arr[i]);
        }
        return list;
    }


    /**
     * 找到基准元素， 也就是第一个被添加进去的元素的索引
     *
     * @param arr
     * @param x
     * @return
     */
    public int findBase(int[] arr, int x) {
        int l = 0, r = arr.length - 1;
        while (r - l > 1) {
            int mid = (r - l) / 2 + l;
            if (arr[mid] == x) {
                return mid;
            }
            if (x < arr[mid]) {
                r = mid;
            } else {
                l = mid;
            }
        }
        return x - arr[l] <= arr[r] - x ? l : r;
    }
}
